package com.cango.student.tree;

public class TreeUtil {

    /**
     * 求二叉树的最大深度
     * 递归
     *
     * @param node
     * @return
     */
    public static int maxDeath(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 左深
        int left = maxDeath(node.left);
        // 右深
        int right = maxDeath(node.right);

        // 计算最大值 // 1代表本节点
        return Math.max(left, right) + 1;
    }

    /**
     * 求二叉树的最小深度
     * 递归
     *
     * @param root
     * @return
     */
    public static int getMinDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getMin(root);
    }

    public static int getMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        // 最终节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 1代表本节点
        return Math.min(getMin(root.left), getMin(root.right)) + 1;
    }


    /**
     * 求二叉树中节点的个数
     *
     * @param root
     * @return
     */
    public static int numOfTreeNode(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = numOfTreeNode(root.left);
        int right = numOfTreeNode(root.right);
        // 1代表本节点
        return left + right + 1;
    }

    /**
     * 求二叉树中叶子节点的个数
     *
     * @param root
     * @return
     */
    public static int numsOfNoChildNode(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 一个节点
        if (root.left == null && root.right == null) {
            return 1;
        }
        return numOfTreeNode(root.left) + numOfTreeNode(root.right);
    }

    public static void main(String[] args) {
        System.out.println(maxDeath(root));
        System.out.println(getMinDepth(root));
        System.out.println(numOfTreeNode(root));
        System.out.println(numsOfNoChildNode(root));
    }

    static TreeNode root;

    static {
        root = new TreeNode();
        root.setVal(0);

        TreeNode l1 = new TreeNode();
        root.setVal(1);

        TreeNode r1 = new TreeNode();
        root.setVal(1);

        root.setLeft(l1);
        root.setRight(r1);

        TreeNode l2 = new TreeNode();
        root.setVal(2);

        TreeNode r2 = new TreeNode();
        root.setVal(1);

        l1.setLeft(l2);
        r1.setRight(r2);

        TreeNode r3 = new TreeNode();
        root.setVal(3);

        r2.setRight(r3);
    }
}
